﻿#include <iostream>

using namespace std;

#define MAX(a, b) (a > b ? a : b)
#define MIN(a, b) (a < b ? a : b)

static int defensive(const int* pCards, const int size, int left, int right);

// 先手
static int initiative(const int* pCards, const int size, int left, int right)
{
	if (left == right) return pCards[left];

	int leftFirst = pCards[left] + defensive(pCards, size, left + 1, right);
	int rightFirst = pCards[right] + defensive(pCards, size, left, right - 1);
	return MAX(leftFirst, rightFirst);
}

// 后手
static int defensive(const int* pCards, const int size, int left, int right)
{
	if (left == right) return 0;

	int leftFirst = initiative(pCards, size, left + 1, right);
	int rightFirst = initiative(pCards, size, left, right - 1);
	return MIN(leftFirst, rightFirst);
}

static int byStrictTable(const int* pCards, const int size)
{
	int dpSize = size * size * sizeof(int);
	int* initiativeDp = (int*)malloc(dpSize);
	memset(initiativeDp, 0, dpSize);
	int* defensiveDp = (int*)malloc(dpSize);
	memset(defensiveDp, 0, dpSize);

	// dp[right][left] = dp[left + right * size]
	for (int i = 0; i < size; i++)
	{
		initiativeDp[i + i * size] = pCards[i];
	}

	for (int i = 0; i < size; i++)
	{
		defensiveDp[i + i * size] = 0;
	}
	
	for (int offset = 1; offset < size; offset++)
	{
		for (int left = 0; left < size; left++)
		{
			// (0,1)->(1,1),(0,0)
			// (1,2)->(2,2),(1,1)
			// (2,3)->(3,3),(2,2)
			// ...
			// (0,2)->(1,2),(1,1)
			// (1,3)->(2,3),(1,2)
			// ...

			int leftIndex = left;
			int rightIndex = left + offset;
			if (rightIndex < size)
			{
				int leftFirst = pCards[leftIndex] + defensiveDp[leftIndex + 1 + rightIndex * size];
				int rightFirst = pCards[rightIndex] + defensiveDp[leftIndex + (rightIndex - 1) * size];
				initiativeDp[leftIndex + rightIndex * size] = MAX(leftFirst, rightFirst);

				leftFirst = initiativeDp[left + 1 + rightIndex * size];
				rightFirst = initiativeDp[left + (rightIndex - 1) * size];
				defensiveDp[leftIndex + rightIndex * size] = MIN(leftFirst, rightFirst);
			}
		}
	}

	int res = MAX(initiativeDp[0 + (size - 1) * size], defensiveDp[0 + (size - 1) * size]);

	free(initiativeDp);
	free(defensiveDp);

	return res;
}

// 给定一个整形数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，
// 但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
//【举例】
// arr = [1, 2, 100, 4]
// 开始时，玩家A只能拿走1或4.如果开始时玩家A拿走1，则排列变为[2, 100, 4], 接下来玩家B可以拿走2或4，然后继续轮到玩家A...
// 如果开始时玩家A拿走4，则排列变为[1, 2, 100], 接下来玩家B可以拿走1或100，然后继续轮到玩家A...
// 玩家A作为绝顶聪明的人不会先拿4，因为拿4之后，玩家B将拿走100.所以玩家A会先拿1，让排列变为[2, 100, 4], 
// 接下来玩家B不管怎么选，100都会被玩家A拿走。玩家A会获胜，分数为101。所以返回101.
// arr = [1, 100, 2]
// 开始时，玩家A不管拿1还是2，玩家B作为绝顶聪明的人，都会把100拿走。玩家B会获胜，分数为100.所以返回100.
int main_CardsInLine()
{
	int cards[] = { 1, 2, 50, 100, 4, 90 };
	int size = sizeof(cards) / sizeof(int);
	int init = initiative(cards, size, 0, size - 1);
	int defen = defensive(cards, size, 0, size - 1);
	int best = MAX(init, defen);
	printf("%d,%d\n", best, byStrictTable(cards, size));
	return 0;
}